package four.sum.count.is.zero;

import java.util.HashMap;
import java.util.Map;

/**
 * @Time 2020/1/3
 * @author 王光浩
 * @Need 给出四个整型的list，找出所有可能的的数据组，数据组需要满足相加之和为0，并且数据中只能有四个元素
 * 		 分别来自于四个list。
 * @Thinking HashMap+暴力解决法。
 *           思路：创建HashMap，key为第四个List元素值，value为元素出现的次数使用三层循环将前面三个list所有
 *           值累加，然后判断0-累加和是否存在于HashMap中，如果存在则将计数器加上对应元素的value。
 *           复杂度分析：时间复杂度O（n^3），空间复杂度O（n），n为list的长度。（用空间换取时间）
 *           结果：超出时间限制。
 */
public class MyMethodTwo {
    public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
    	Map<Integer,Integer> count=new HashMap<Integer,Integer>();
    	int key;
    	int total=0;    //统计组数
    	//将第四个list加入HashSet
    	for(int i:D) {
    		count.put(i, count.getOrDefault(i, 0)+1);
    	}
    	//计算组数
    	for(int i:A) {
    		for(int j:B) {
    			for(int z:C) {
    				key=0-i-j-z;
    				//存在符合要求的组
    				if(count.containsKey(key)) {
    					total+=count.get(key);
    				}
    			}
    		}
    	}
    	return total;
    }

}
